Search Results

Documents authored by Gotoh, Tsuyoshi


Document
Tight Bounds on Distributed Exploration of Temporal Graphs

Authors: Tsuyoshi Gotoh, Paola Flocchini, Toshimitsu Masuzawa, and Nicola Santoro

Published in: LIPIcs, Volume 153, 23rd International Conference on Principles of Distributed Systems (OPODIS 2019)


Abstract
Temporal graphs (or evolving graphs) are time-varying graphs where time is assumed to be discrete. In this paper, we consider for the first time the problem of exploring temporal graphs of arbitrary unknown topology. We study the feasibility of exploration, under both the Fsync and Ssync schedulers, focusing on the number of agents necessary and sufficient to explore such graphs. We first consider the minimal (i.e., less restrictive) assumption on the dynamics of the graph under which exploration is still feasible: temporal connectivity. Let ℋ be the class of temporally connected graphs; we show that for any temporal graph ? ∈ ℋ the number of agents sufficient to perform exploration is related to the number of its transient edges, a parameter η(?) we call evanescence of the graph. More precisely, any ? ∈ ℋ can be explored by a team of k ≥ 2 η(?) +1 agents; this bound is tight as we prove there are ? ∈ ℋ that cannot be explored by 2 η(?) agents. We then turn our attention to the well-known stronger assumption on the dynamics of the graph, called 1-interval connectivity: the graph is connected at any time step. Let ? ⊂ ℋ be the class of these always-connected temporal graphs. For this class, we prove the existence of a difference between Fsync and Ssync when there is a bound ? on the number of edges missing at each time. In fact, we show a tight bound of 2 ? +1 on the number of agents necessary and sufficient in Ssync, and a smaller tight bound of 2 ? in Fsync. As a corollary, we re-establish two recently published bounds for 1-interval connected rings.

Cite as

Tsuyoshi Gotoh, Paola Flocchini, Toshimitsu Masuzawa, and Nicola Santoro. Tight Bounds on Distributed Exploration of Temporal Graphs. In 23rd International Conference on Principles of Distributed Systems (OPODIS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 153, pp. 22:1-22:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{gotoh_et_al:LIPIcs.OPODIS.2019.22,
  author =	{Gotoh, Tsuyoshi and Flocchini, Paola and Masuzawa, Toshimitsu and Santoro, Nicola},
  title =	{{Tight Bounds on Distributed Exploration of Temporal Graphs}},
  booktitle =	{23rd International Conference on Principles of Distributed Systems (OPODIS 2019)},
  pages =	{22:1--22:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-133-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{153},
  editor =	{Felber, Pascal and Friedman, Roy and Gilbert, Seth and Miller, Avery},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2019.22},
  URN =		{urn:nbn:de:0030-drops-118082},
  doi =		{10.4230/LIPIcs.OPODIS.2019.22},
  annote =	{Keywords: Distributed algorithm, Mobile agents, Exploration of dynamic networks, Arbitrary footprint}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail